// 提交链接 https://leetcode.cn/problems/min-cost-climbing-stairs/submissions/530189327/
// 746. 使用最小花费爬楼梯
// 完成日期： 2024.9.8
// c++ 动态规划枚举上一步所在的台阶

class Solution {
public:
    unordered_map<int, pair<int, int>> dp;
    int minCostClimbingStairs(vector<int>& cost) {
        return dfs(cost.size(), cost);
    }
    int dfs(int i, vector<int>& cost)
    {
        if (dp[i].first) return dp[i].second;
        if (i == 0 || i == 1) return 0;
        int ans = min(dfs(i - 1, cost) + cost[i - 1], dfs(i - 2, cost) + cost[i - 2]);
        dp[i].first = 1;
        return dp[i].second = ans;
    }
};